package com.algorithms.linkedlists;

/**
 * this sorted linked list works with measurable data like
 * Integer, Long, Float, Double or String.
 * 
 * @author minhld
 *
 * @param <T>
 */
public class SortedLinkedList<T extends Comparable<T>> {
	private Link<T> first;
	
	public SortedLinkedList(){
		this.first = null;
	}
	
	public SortedLinkedList(Link<T> first){
		this.first = first;
	}
	
	public Link<T> getFirst(){
		return this.first;
	}
	
	/**
	 * insert a link at first position
	 * 
	 * @param content
	 */
	public void insert(T content){
		Link<T> newLink = new Link<>(this.first, content);
		
		if (isEmpty()){
			// if the linked list is empty
			this.first = newLink;
			return;
		}else{
			Link<T> prev = null;
			Link<T> current = this.first;

			// move forward to find position to insert
			while (current != null && 
					content.compareTo(current.getContent()) > 0){
				prev = current;
				current = current.getNext();
			}
			
			// insert
			if (prev == null){
				// if the inserting item is smaller than the first
				// item in the list
				newLink.setNext(this.first);
				this.first = newLink;
			}else{
				// when inserting item is inserted in the middle
				prev.setNext(newLink);
				newLink.setNext(current);
			}
		}
		
	}
	
	/**
	 * delete a link in list and return that one
	 * 
	 * @return deleted link
	 */
	public Link<T> deleteFirst(){
		if (isEmpty()){
			System.err.println("no more items to delete");
			return null;
		}
		
		Link<T> deletedLink = this.first;
		this.first = this.first.getNext();
		return deletedLink;
	}
	
	public Link<T> find(T contentKey){
		// check if list is empty
		if (isEmpty()){
			return null;
		}
		
		// check the first element of list
		Link<T> currLink = this.first;
		if (currLink.getContent().equals(contentKey)){
			return currLink;
		}
		
		while (currLink.getNext() != null){
			// move to next element (if available) and check
			currLink = currLink.getNext();
			if (currLink.getContent().equals(contentKey)){
				return currLink;
			}
		}
		
		// item not found
		return null;
	}
	
	public Link<T> delete(T contentKey){
		// check if list is empty
		if (isEmpty()){
			return null;
		}
		
		// check the first element of list
		Link<T> currLink = this.first;
		if (currLink.getContent().equals(contentKey)){
			return deleteFirst();
		}
		
		Link<T> prevLink;
		while (currLink.getNext() != null){
			prevLink = currLink;
			// move to next element (if available) and check
			currLink = currLink.getNext();
			if (currLink.getContent().equals(contentKey)){
				prevLink.setNext(currLink.getNext());
				return currLink;
			}
		}
		
		// item not found
		return null;
	}
	
	public boolean isEmpty(){
		return this.first == null;
	}
	
	public void printElements(){
		if (isEmpty()){
			System.out.println("The linked list is empty");
			return;
		}
		
		// print first
		Link<T> currLink = this.first;
		System.out.print(currLink.getContent() + ", ");
		
		while (currLink.getNext() != null){
			// move to next element (if available) and print
			currLink = currLink.getNext();
			System.out.print(currLink.getContent() + ", ");
		}
	}
}
